package com.demo.jzoffer2;

import org.junit.Test;

/**
 * @author gy
 * @date 2023/02
 */
public class Test0210_02 {
    /**
     * 输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
     *
     * 要求时间复杂度为O(n)。
     *
     * 输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
     * 输出: 6
     * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
     * @param nums
     * @return
     */
    public int maxSubArray(int[] nums) {
        // 动态规划：无非就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存
        // 一般是用 一维数组 或者 二维数组来保存

        int length = nums.length;
        // 特例处理
        if (length == 0){
            return 0;
        }
        int[] dp = new int[length];
        // 第三步：找出初始值
        dp[0] = nums[0];
        int res = nums[0];
        // 动态规划 三步走
        // 第一步：定义数组元素的含义
        // dp[i] 以第i个数结尾的 连续子数组的最大和
        for (int i = 1; i < length; i++) {
            // 第二步：找出数组元素之间的关系
            int a = dp[i - 1];
            int b = nums[i];
            int c = a + b;
            int d = dp[i] = Math.max(dp[i - 1] + nums[i],nums[i]);
            res = Math.max(res,dp[i]);
            System.out.println("res"+i+"="+res);
        }
        return res;
    }


    @Test
    public void m1() {
       int[] nums = {-2,1,-3,4,-1,5,8,2,1,-5,4};
        System.out.println(maxSubArray(nums));
    }

    @Test
    public void m2() {
        String a = "sdfjlkasfl.aaa";
        String substring = a.substring(0, a.indexOf(".aaa"));
        System.out.println(substring);
    }

}
